1804H - Code Lock - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int c[16][16],d[16][1<<16],k,n;
char s[100004];int L,R,ans=1e9;ll cnt;
int a[8],b[8],mp[256],mq[256],vp[256],vq[256];
int f[256][256];ll g[256][256];
int A[17][3000],B[17][3000],SZ[17];
int main(){
	scanf("%d%d%s",&k,&n,s+1);for(int i=1;i<n;i++)c[s[i]-'a'][s[i+1]-'a']++,c[s[i+1]-'a'][s[i]-'a']++;
	for(int i=0;i<k;i++)for(int j=1;j<(1<<k);j++){int t=__builtin_ctz(j);d[i][j]=d[i][j^1<<t]+c[i][t];}
	R=k>>1,L=k-R;for(int i=1;i<=k;i++){int rd=i>>1,ld=i-rd;
		for(int x=0;x<1<<L;x++)if(__builtin_popcount(x)==ld&&x&1)
			for(int y=0;y<1<<R;y++)if(__builtin_popcount(y)==rd)A[i][SZ[i]]=x,B[i][SZ[i]++]=y;
	}
	for(int C=1;C<(1<<k);C++)if(C&1&&__builtin_popcount(C)==L){
		for(int i=0,ia=0,ib=0;i<k;i++){if(C>>i&1)a[ia++]=i;else b[ib++]=i;}
		memset(vp,0,sizeof(vp)),memset(vq,0,sizeof(vq)),memset(f,0x3f,sizeof(f));
		for(int i=1;i<1<<L;i++){
			int t=__builtin_ctz(i);mp[i]=mp[i^1<<t]|1<<a[t];
			for(int j=0;j<L;j++)if(!(i>>j&1))vp[i]+=d[a[j]][mp[i]];
		}
		for(int i=1;i<(1<<R);i++){
			int t=__builtin_ctz(i);mq[i]=mq[i^1<<t]|1<<b[t];
			for(int j=0;j<R;j++)if(!(i>>j&1))vq[i]+=d[b[j]][mq[i]];
		}
		int al=mp[(1<<L)-1],ar=mq[(1<<R)-1];
		f[1][0]=vp[1],g[1][0]=1;
		for(int i=2;i<=k;i++){
			int pr=(i>>1)-1,pl=i-pr-2;
			for(int j=0;j<SZ[i-1];j++){
				int x=A[i-1][j],y=B[i-1][j];
				if(!(i&1)){
					for(int c=0;c<R;c++)if(!(y>>c&1)){
						int z=y|1<<c,w=f[x][y]+d[b[c]][mp[x]]*(R-pr)+d[b[c]][al^mp[x]]*pr+vq[z];
						if(w<f[x][z])f[x][z]=w,g[x][z]=g[x][y];
						else if(w==f[x][z])g[x][z]+=g[x][y];
					}
				}else{
					for(int c=0;c<L;c++)if(!(x>>c&1)){
						int z=x|1<<c,w=f[x][y]+d[a[c]][mq[y]]*(L-pl)+d[a[c]][ar^mq[y]]*pl+vp[z];
						if(w<f[z][y])f[z][y]=w,g[z][y]=g[x][y];
						else if(w==f[z][y])g[z][y]+=g[x][y];	
					}
				}
			}
		}
		for(int i=0;i<SZ[k];i++){
			int x=A[k][i],y=B[k][i];
			if(f[x][y]<ans)ans=f[x][y],cnt=g[x][y];
			else if(ans==f[x][y])cnt+=g[x][y];
		}
	}
	printf("%d %lld",ans+n,cnt);
}